package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 61. 旋转链表
 * @date 2025/3/14 13:46
 */
public class E61 {

    /**
     * <h3>方法一：用循环找到指定节点，修改指针</h3>
     *
     * @param head 头节点
     * @param k    旋转次数（循环右移）
     * @return 旋转后的头节点
     */
    public ListNode rotateRight(ListNode head, int k) {
        // 1. 先判定头节点是否为空，为空直接返回null
        if (head == null) return null;
        // 2. 计算链表长度、实际右移次数，如果不判断head == null这里会报错除以0的错误
        int length = lengthOf(head);
        int actualK = k % length;
        // 3. 如果实际右移次数为0，直接返回头节点
        if (actualK == 0) return head;
        // 4. 找到新尾节点，旧尾节点，新头节点
        ListNode newTail = findNode(head, length - actualK - 1);
        ListNode oldTail = findNode(head, length - 1);
        ListNode newHead = newTail.next;
        // 5. 修改指针指向
        newTail.next = null;
        oldTail.next = head;
        // 6. 返回新头节点
        return newHead;
    }

    /**
     * 查找指定索引的节点（索引从0开始）
     *
     * @param head  头节点
     * @param index 索引
     * @return 指定索引查找到的节点
     */
    private ListNode findNode(ListNode head, int index) {
        ListNode curr = head;
        // index次就行了，最后一次循环会有一次curr.next
        for (int i = 0; i < index; i++) {
            curr = curr.next;
        }
        return curr;
    }

    /**
     * 计算链表长度
     *
     * @param head 头节点
     * @return 链表长度
     */
    private int lengthOf(ListNode head) {
        ListNode curr = head;
        int length = 0;
        while (curr != null) {
            curr = curr.next;
            length++;
        }
        return length;
    }
}
